package tree;

/**
 * @author way
 * @create 2025-02-13 10:03
 */
public class _654_constructMaximumBinaryTree {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length);
    }

    private TreeNode build(int[] nums, int leftIndex, int rightIndex) {
        if (leftIndex == rightIndex) return null;

        int maxIndex = leftIndex;
        int maxVal = nums[leftIndex];
        for (int i = leftIndex + 1; i < rightIndex; i++) {
            if (nums[i] > maxVal) {
                maxVal = nums[i];
                maxIndex = i;
            }
        }

        TreeNode root = new TreeNode(maxVal);
        root.left = build(nums, leftIndex, maxIndex);
        root.right = build(nums, maxIndex + 1, rightIndex);

        return root;
    }
}
